"""
nums=[1,5,11,5]
target=sum(nums)//2
dp=[[False for _ in range(target+1)]for _ in range(len(nums))]
print(dp)

"""
class Solution:
    def canPartition(self,nums):
        if sum(nums)%2==1:
            return False
        target =sum(nums)//2
        dp=[[False for _ in range(target+1)]for _ in range(len(nums))]

        if nums[0]<=target:
            dp[0][nums[0]]=True
        for i in range(1,len(nums)):
            for j in range(0,target+1):
                dp[i][j]=dp[i-1][j]
                if nums[i]==j:
                    dp[i][j]=True #如果第i个元素恰好等于当前背包容量j
                    continue
                if nums[i]<j:
                    dp[i][j]=dp[i-1][j] or dp[i-1][j-nums[i]]
        return dp[len(nums)-1][target]
if __name__=='__main__':
    nums=[1,5,11,6]
    s=Solution()
    print(s.canPartition(nums))